//给你两个 非空 的链表，表示两个非负的整数。
// 它们每位数字都是按照 逆序 的方式存储的，
// 并且每个节点只能存储 一位 数字。
//
// 请你将两个数相加，并以相同形式返回一个表示和的链表。 
//
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 
//
// 示例 1： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[7,0,8]
//解释：342 + 465 = 807.
// 
//
// 示例 2： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 示例 3： 
//
// 
//输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
//输出：[8,9,9,9,0,0,0,1]
// 
//
// 
//
// 提示： 
//
// 
// 每个链表中的节点数在范围 [1, 100] 内 
// 0 <= Node.val <= 9 
// 题目数据保证列表表示的数字不含前导零 
// 
// Related Topics 递归 链表 数学 
// 👍 5947 👎 0

package leetcode.editor.cn;

import java.math.BigInteger;

//Java：两数相加
public class AddTwoNumbers_2 {
    public static void main(String[] args) {
        Solution solution = new AddTwoNumbers_2().new Solution();
        //ListNode node = solution.addTwoNumbers(create(new int[]{2, 4, 3}), create(new int[]{5, 6, 4}));
        ListNode node = solution.addTwoNumbers(create(new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 1}), create(new int[]{5, 6, 4}));
        System.out.println(getValue(node));
    }

    public static String getValue(ListNode listNode) {
        if (listNode.next == null) {
            return listNode.val + "";
        } else {
            return getValue(listNode.next) + listNode.val;
        }
    }

    public static ListNode create(int[] num) {
        ListNode node = new ListNode(num[num.length - 1]);
        if (num.length == 1) {
            return node;
        }
        for (int i = num.length - 2; i >= 0; i--) {
            node = new ListNode(num[i], node);
        }
        return node;
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     * 解题思路: 同位相加，ListNode是从个位开始，依次递归。和如果大于10，则进位加1。
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            return getValue(l1, l2, 0);
        }

        public ListNode getValue(ListNode l1, ListNode l2, int i) {
            if (l1 == null && l2 == null && i == 0) {
                return null;
            }

            ListNode n1 = null, n2 = null, result;
            int i1 = 0, i2 = 0;
            if (l1 != null) {
                n1 = l1.next;
                i1 = l1.val;
            }
            if (l2 != null) {
                n2 = l2.next;
                i2 = l2.val;
            }

            int r = i1 + i2 + i;
            if (r > 9) {
                result = new ListNode(r - 10, getValue(n1, n2, 1));
            } else {
                result = new ListNode(r, getValue(n1, n2, 0));
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}